// https://leetcode.cn/problems/4sum/description/

// 算法思路总结：
// 1. 先对数组进行排序
// 2. 四层循环优化为三层（固定cd，双指针ab）
// 3. 使用长整型防止整数溢出
// 4. 跳过重复元素避免重复解
// 5. 时间复杂度：O(n³)，空间复杂度：O(1)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>

class Solution 
{
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) 
    {
        sort(nums.begin(), nums.end());

        int n = nums.size();
        vector<vector<int>> ret;

        for (int d = n - 1 ; d >= 3 ; ) 
        {
            for (int c = d - 1 ; c >= 2 ; ) 
            {
                long long goal = (long long)target - nums[c] - nums[d];
                for (int a = 0, b = c - 1 ; a < b ; )
                {
                    long long sum = (long long)nums[a] + nums[b];
                    if (sum == goal)
                    {
                        ret.push_back({nums[a], nums[b], nums[c], nums[d]});
                        a++;
                        b--;
                        while (a < b && nums[b] == nums[b + 1])
                            b--;
                        while (a < b && nums[a] == nums[a - 1])
                            a++;
                    }
                    else if (sum > goal)
                    {
                        b--;
                        while (a < b && nums[b] == nums[b + 1])
                            b--;
                    }
                    else
                    {
                        a++;
                        while (a < b && nums[a] == nums[a - 1])
                            a++;
                    }
                }
                c--;
                while (c >= 2 && nums[c] == nums[c + 1])
                    c--;
            }
            d--;
            while (d >= 3 && nums[d] == nums[d + 1])
                d--;
        }
        return ret;
    }
};

int main()
{
    vector<int> v1 = {1, 0, -1, 0, -2, 2}, v2 = {2, 2, 2, 2, 2};
    int t1 = 0, t2 = 8;

    Solution sol;
    auto vv1 = sol.fourSum(v1, t1), vv2 = sol.fourSum(v2, t2);

    for (const auto &v : vv1)
    {
        for (const auto &num : v)
            cout << num << " ";
        cout << endl;
    }
    cout << endl;

    for (const auto &v : vv2)
    {
        for (const auto &num : v)
            cout << num << " ";
        cout << endl;
    }

    return 0;
}